// #define print(...)

#define kstr(i) keys[ (i)-'2' ]
class Solution {
public:
vector<string> letterCombinations(string digits) {
    vector<string> res;
    if(digits.empty()) return res;
    string keys[] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    string ans;
    function<void(size_t)> bt;
    bt = [&](size_t index){
        if(index == digits.length()){
            res.push_back(ans);
            return;
        }
        for(auto &c:kstr(digits[index])){
            ans.push_back(c);
            bt(index+1);
            ans.pop_back();
        }
    };
    bt(0);
    return res;
}
};
